1. Field of Invention
The present invention relates to a method of encoding a color image to display the color image on a personal computer, a portable terminal, or the like and an encoding device therefor, and a method of decoding the color image and a decoding device therefor.
2. Description of Related Art
Conventionally, when a color image is encoded or decoded, a palette is provided which is formed of a predetermined number of colors. An index is assigned in the palette for each pixel, and the color image is encoded and decoded by encoding and decoding the index.
For example, in a personal computer, game equipment, or the like, an image called a multi-color image is used. The multi-color image is also called a representative color image, a limited color image, or the like. As shown in FIG. 15, these are images for which indexes are assigned to specified colors, that is, colors having specified values of R (red), G (green), and B (blue), and which are expressed by a representative color which is limited to 16 colors, 256 colors, or the like by using the data of the indexes.
In this type of the data of the multi-color image, if each color of R, G, and B is hypothetically expressed by 8 bits (256 groups), a total of 24 bits is needed. However, because the index itself is displayed, for example, by 8 bits, the compression percentage is relatively high. However, the amount of information is still large regardless of the compression. Thus, if the information is processed as-is without any consideration, the required memory capacity becomes large and the communication rate becomes slow so that it is not practical. Therefore, the compression technology is extremely important in the multi-color image as well as in other image data. In particular, the number of colors is limited in the multi-color image so that lossless encoding and decoding, that is, a reversible compression technique is needed.
Recently, the technology of using an entropy encoder and decoder has been focused upon as a method of data compression. One example of the entropy encoding and decoding technology is a technology of arithmetical encoding and decoding. The gist of this technology is disclosed, for example, in Japanese Patent Laid-Open Publication Nos. Sho 62-185413, Sho 63-74324, Sho 63-76525, and the like.
FIGS. 20A and 20B show a conventional multi-color image encoding system 50 and decoding system 60 which uses this type of technology. The encoding system 50 includes a line buffer 51 and an entropy encoder 52. The data of the index to be input, that is, the color pixel data 100A, is input to the line buffer 51 and the entropy encoder 52. The color pixel data 100A is input as sequential pixel data in a horizontal scanning order which is raster-scanned as shown in FIG. 21.
Furthermore, as a method for creating the data of the index, that is, the color pixel data 100A, the method to apply the index in order of the color to be input is common. As shown in FIG. 19, phenomena occur such that the colors are significantly different even if the numbers of the index are close (e.g., xe2x80x9c1xe2x80x9dand xe2x80x9c2xe2x80x9d) and the colors are close even if the numbers of the index are distant (e.g., xe2x80x9c100xe2x80x9d and xe2x80x9c200xe2x80x9d). In order to avoid these phenomena, as shown in Japanese Patent Laid-Open Publication No. Hei 5-328142, there is also a method to apply a sequential number to the approximate color.
The line buffer in the encoding system 50, which functions as a reference pixel formation means, forms the reference pixel data A, B, C, and D for an encoding object pixel X, i.e., that is to be encoded, from the color pixel data 100A which was already input. That is, the line buffer 51 stores the history of a portion that includes n lines (approximately 1-5 lines are commonly used) when scanning the image. Furthermore, every time the color pixel data 100A of the encoding object pixel X is input, a series of pixel data which is formed by the previous pixel A and the surrounding pixels B, C, and D is output to the entropy decoder 52 as reference pixel data 110.
The entropy encoder 52 is formed by using methods such as an arithmetical encoding and Huffmnan encoding. Furthermore, the reference pixel data 110 is used as a state signal and the object color pixel data 100A is converted and output to the encoding data 200.
Meanwhile, the decoding system 60 is structured so as to include a line buffer 61 and an entropy decoder 62. At this point, the line buffer 61 and the entropy decoder 62 are formed so as to decode and output the encoded data 200 to be input in the completely reverse order of the line buffer 51 and the entropy encoder 52 of the encoding system 50.
Thus, the encoding system 50 and the decoding system 60 use algorithms which are completely opposite to each other and encode the color pixel data 100A to the encoded data 200. Furthermore, it is possible to output the encoded data 200 by decoding the encoded data 200 to the color pixel data 100B. Therefore, the system can be widely used for various uses.
Here, one example of an arithmetical encoding type of the entropy encoder 52 which is used in the system of FIG. 20A is shown in FIG. 22. Moreover, the structure of the entropy decoder 62 of the arithmetical encoding type is substantially the same as the structure of the entropy encoder 52, so the explanation is omitted here.
The entropy encoder 52 is structured so as to include an arithmetical operation part 55 and a generation probability formation means 56 which functions as a state memory device. In the generation probability formation means 56, in order to determine the symbol generation number probability which is needed for encoding, a state parameter table is written. The above-written state parameter is specified by the state signal to be input. Moreover, for the table of the state parameter, which was specified by the state signal, the generation probability operation parameter of the generation probability formation means 56 is output to the arithmetical operation part 55.
Based upon the generation probability which is thus input, the arithmetical operation part 55 performs entropy encoding, and the color pixel data 100A to be input is converted and output as the encoded data 200. Moreover, the generation probability is re-calculated for the state signal by the value of the encoded color pixel data 100A and is input to the generation probability formation means 56 as an operation parameter update value. The update result is stored in the table as the generation probability of the following data so that the compression efficiency of the entropy encoder 52 improves.
Unlike this type of encoding of a multi-color image, a natural image is fetch-encoded by a scanning device and changed to a multi-color image. In a case like this, in order to efficiently encode the color image, various methods and devices are suggested. For example, in Japanese Patent Laid-Open Publication No. Hei 6-178122, the read image is identified in block units as to whether it is a binary area or a multi-value area, and the respective encoded data of binary image, multi-value image (=natural image), and area information is formed.
Furthermore, in Japanese Patent Laid-Open Publication No. Hei 8-9163, the input color image data is divided into blocks of 16xc3x9716 pixels, and it is checked whether each block is a color area or a black-and-white area. With respect to a block of a color area, after sampling is performed in a predetermined sub-sampling ratio, DCT conversion, linear quantization, and entropy encoding are performed. Meanwhile, with respect to a block of a black-and-white area, only the Y component of the color components YCrCb which form the color image data is performed by DCT conversion, linear quantization, and entropy encoding.
Moreover, as a method of compression of two-dimensional image data, using the data information of the previous line is also known (see Japanese Patent Laid-Open Publication No. Hei 7-336696). This technology is to output the data of the length and the position of a partial data row on a previous line as data of that partial data row when data of a previous line and the same partial data row which is one pixel exist.
However, in the conventional multi-color image and natural image general encoding and decoding devices, various types of compression technologies are used and the encoded and decoded data amount is significantly reduced, but no solution to this problem has been developed in terms of the data capacity for the palette. That is, in the conventional color image encoding and decoding devices, when the number of colors to be used is increased, the data capacity for the image increases and the refresh rate for the image display tends to be slow. For example, when a color image of 256xc3x97256 pixels is encoded or decoded by 256 colors, a memory of 66,304 bytes is needed. That is, when each color needs a total of three bytes in RGB, 256xc3x973 bytes +256xc3x97256xc3x971 byte (256 colors)=66,304 bytes is established. Thus, in the case of a screen with the 256xc3x97256 pixels, even if 256 colors are used, it requires a large capacity of approximately 70 Kbytes and becomes a relatively large amount of data even by using various kinds of complicated compression means. Because of this, when the refresh rate becomes slow, the memory for the display becomes large.
Furthermore, in the prior art as disclosed in Japanese Patent Laid-Open Publication Nos. Hei 6-178122 and Hei 8-9163, because the color image is divided into blocks, since it is divided into black-and-white areas and color areas, and encoded according to these areas, the encoding efficiency improves, but the encoding efficiency does not improve when most of the areas are color areas. In addition, the number of colors to be maintained in order to display the image is the same as the conventional method and a large data capacity of data is required. Moreover, in the compression technology disclosed in Japanese Patent Laid-Open Publication No. Hei 7-336696, the compression efficiency improves when the same pattern continues in the upper and lower directions, but the compression rate does not improve at all when pixels which are different for each line continue in the vertical direction.
An object of the present invention is to provide a color image encoding method which can improve the refresh rate and minimize the memory for display, and an encoding device, and a color image decoding method and a decoding device for when the color image is reproduced. Furthermore, another object of the present invention is to provide a color image encoding method and an encoding device that improves the compression rate and the decoding efficiency of the image and the encoding device, and also to provide a corresponding color image decoding method and decoding device.
In order to achieve the above objects, in the present invention, a color image encoding method which inputs and encodes color image data includes the steps of counting the number of colors used in the input color image data, creating a global pallet in which indexes corresponding to respective colors are listed when the number of colors used is a predetermined value or less, dividing the input color image data into a plurality of blocks, creating a local palette in which the indexes in the global palette are listed when the number of colors in a block is less than the number of colors in the global palette, assigning the indexes in the global palette to the input pixels when the number of colors in the block is the same as the number of colors in the global palette and which otherwise assigns the indexes in the local palette to the input pixels, and encoding the color indexes, wherein, when the predetermined value is 2n (n is 2x when x is an integer equal to or greater than 0), the indexes in the global palette are expressed by n bits, and when the number of colors in the block is 2m (m is 2x where x is an integer equal to or greater than 0, however, m is an integer equal to or greater than a specified value when m is equal to or greater than said specified value), the index in the local palette is expressed by m bits, and wherein the local palette is not created when n=m, and the local palette is created when n greater than m.
Because of this, when the color image encoding method is used, the data which becomes the object of encoding is significantly reduced and it is possible to minimize the data capacity. Because of this, it is possible to use a simple compression method and improve the refresh rate. Moreover, prior to the image display, it is possible to perform decoding of only the block which is needed for display, and to minimize the memory for display. Furthermore, it is possible to display the number of colors in the global palette and local palette with numbers of bits such as 1, 2, 4, 8, 16, and 32, respectively, and to improve the processing efficiency when the encoding process is performed in a CPU. Moreover, when m is the specified value or more, it is possible to control the capacity of the data which indicates the indexes because the value of m increases by one bit unit.
Moreover, in the present invention, in the color image encoding method, the predetermined value is set at 256 colors, the specified value is set at 5, and the size of one block is set at 32xc3x9732 pixels.
When the block size is set at 32xc3x9732 pixels, the maximum becomes 1,024 colors, and most images are accommodated within 256 colors. Thus, by setting the predetermined value at 256 colors, the present invention applies to most images and it is possible to reduce the memory and improve the refresh rate. Furthermore, when the number of colors in the block exceeds 16 colors and stays less than 32 colors, it can be expressed by five bits, when the number of colors exceeds 32 colors and stays less than 64 colors, it can be expressed by six bits, when the number of colors exceeds 64 colors and stays less than 128 colors, it can be expressed by 7 bits. It is possible to control the data capacity required for the color indexes to a small size. In particular, data such as a map has approximately 20 colors in many cases, so in the case of data like that, it can be expressed by five bits, and it is possible to definitely minimize the capacity compared to eight bits when m is the x square of 2. In addition, when run length encoding is performed, 16 can be used as a maximum number of runs and it can be processed by four bits at that time.
Furthermore, in the present invention, a color image encoding device which inputs and encodes the color image data comprises a global palette creation means which counts the number of colors used in the input color image data and creates a global palette in which indexes corresponding to respective colors are listed when the number of colors used is a predetermined value or less, a block division means which divides the input color image data into a plurality of blocks, a local palette creation means which creates a local palette in which the indexes in the global palette are listed when the number of colors in a block is less than the number of colors in the global palette, a color index assigning means which assigns the indexes in the global palette to the input pixels when the number of colors in the block is the same as the number of colors in the global palette and which otherwise assigns the indexes in the local palette to the input pixels, and an encoding process which encodes the color indexes, wherein, when the predetermined value is 2n (n is 2x when x is an integer equal to or greater than 0), the indexes in the global palette are expressed by n bits, and when the number of colors in the block is 2m (m is 2x where x is an integer equal to or greater than 0, however, m is an integer equal to or greater than a specified value when m is equal to or greater than said specified value), the index in the local palette is expressed by m bits, and wherein the local palette is not created when n=m, and the local palette is created when n greater than m.
Because of this, when the color image encoding device is used, the data which becomes the object of encoding is significantly reduced and it is possible to minimize the data capacity. Because of this, it is possible to use a simple compression method and improve the refresh rate. Moreover, prior to the image display, it is possible to perform decoding of only the block which is needed for display, and to minimize the memory for display. Furthermore, it is possible to display the number of colors in the global palette and local palette with numbers of bits such as 1, 2, 4, 8, 16, and 32, respectively, and to improve the processing efficiency when the encoding process is performed in a CPU. Moreover, when m is the specified value or more, it is possible to control the capacity of the data which indicates the index because the value of m increases by one bit unit.
In addition, in the invention, in the color image encoding device, the predetermined value is set at 256 colors, the specified value is set at 5, and the size of one block is set at 32xc3x9732 pixels.
When the block size is set at 32xc3x9732 pixels, the maximum becomes 1,024 colors, and most images are accommodated within 256 colors. Thus, by setting the predetermined value at 256 colors, the present invention applies to most images and it is possible to reduce the memory and improve the refresh rate. Furthermore, when the number of colors in the block exceeds 16 colors and stays less than 32 colors, it can be expressed by five bits, when the number of colors exceeds 32 colors and stays less than 64 colors, it can be expressed by six bits, when the number of colors exceeds 64 colors and stays less than 128 colors, it can be expressed by 7 bits. It is possible to control the data capacity required for the color indexes to a small size. In particular, data such as a map has approximately 20 colors in many cases, so in the case of data like that, it can be expressed by five bits, and it is possible to definitely minimize the capacity compared to eight bits when m is the x square of 2. In addition, when run length encoding is performed, 16 can be used as a maximum number of runs and it can be processed by four bits at that time.
Furthermore, in the present invention, a color image decoding method which decodes the encoded color image data includes the steps of identifying the number of colors used in the entire color image data to be decoded, calling the global palette in which indexes corresponding to respective colors are listed when the number of colors used is a predetermined value or less, and decoding data that was encoded by dividing the color image data into a plurality of blocks, wherein the block decoding step has a number of colors in the block identifying step which identifies the number of colors in the divided blocks, and a conditional alias decoding step which, when the number of colors which was identified by the number of colors in the block identifying step is less than the number of colors in the global palette, a column corresponding to the local palette in which the indexes in the global palette are listed is called from the values of the decoded color indexes and the colors of the global palette which is described in the local palette is decoded, and which, when the number of colors which was identified by the number of colors in the block identifying step is the same as the number of colors in the global palette, directly decodes the colors of the global palette from the values of the color indexes which were decoded, and wherein, when the predetermined value is 2n (n is 2x when x is an integer equal to or greater than 0), the indexes in the global palette are expressed by n bits, and when the number of colors in the block is 2m (m is 2x where x is an integer equal to or greater than 0, however, m is an integer equal to or greater than a specified value when m is equal to or greater than said specified value), the index in the local palette is expressed by m bits, and wherein the local palette is not created when n=m, and the local palette is created when n greater than m.
Because of this, when this color image decoding method, the color data amount at the time of decoding is significantly reduced and it is possible to use a simple decoding method. Because of this, it is possible to improve the refresh rate. Moreover, it is not necessary to decode the entire image, and it is acceptable to reproduce the only the blocks which are needed for display. As a result, it is possible to reduce the memory for display and miniaturize the device which uses this decoding method, and to reduce the cost. Furthermore, it is possible to display the number of colors in the global palette and local palette with numbers of bits such as 1, 2, 4, 8, 16, and 32, respectively, and to improve the processing efficiency when the decoding process is performed in the CPU. Moreover, when m is the specified value or more, it is possible to control the capacity of the data which indicates the indexes because the value of m increases by one bit unit.
Moreover, in the present invention, in the color image decoding method, the predetermined value is set at 256 colors, the specified value is set at 5, and the size of one block is set at 32xc3x9732 pixels.
When the block size is thus set at 32xc3x9732 pixels, the maximum becomes 1,024 colors, and most images are accommodated within 256 colors. Thus, by setting the predetermined value at 256 colors, the present invention applies to most images and it is possible to reduce the memory required and improve the refresh rate. Furthermore, when the number of colors in the block exceeds 16 colors and stays less than 32 colors, it can be expressed by five bits, when the number of colors exceeds 32 colors and stays less than 64 colors, it can be expressed by six bits, when the number of colors exceeds 64 colors and stays less than 128 colors, it can be expressed by 7 bits. It is possible to control the data capacity required for the color indexes to a small size. In particular, data such as a map has approximately 20 colors in many cases, so in such a case, it can be expressed by five bits, and it is possible to definitely minimize the capacity compared to eight bits when m is the x square of 2. In addition, when run length encoding is performed, 16 can be used as a maximum number of runs and it can be processed by four bits at that time.
Furthermore, in the present invention, a color image decoding device which decodes the encoded color image data comprises a number of colors used identifying means which identifies the number of colors used in the entire color image data to be decoded, a global palette maintaining means which maintains a global palette in which indexes corresponding to respective colors are described when the number of colors used is a predetermined value or less, and a block decoding means which decodes the data encoded by dividing the color image data into a plurality of blocks to each block, wherein the block decoding means has a number of colors in the block identifying means which identifies the number of colors in the divided blocks, a local palette maintaining means which maintains a local palette in which indexes within the global palette are listed, and a conditional alias decoding means which, when the number of colors identified by the number of colors in the block identifying means is less than the number of colors in the global palette, calls the column corresponding to the local palette in which the index in the global palette from the value of the decoded color index are listed and decodes the colors of the global palette that are listed in the local palette, directly decodes the colors in the global palette from the values of the decoded color indexes when the number of colors which were identified by the number of colors in the block identifying means is the same as the number of colors in the global palette, wherein, when the predetermined value is 2n (n is 2x when x is the integer equal to or greater than 0), the indexes in the global palette are expressed by n bits, and when the number of colors in the block is 2m (m is 2x where x is an integer equal to or greater than 0, however, m is an integer equal to or greater than a specified value when m is equal to or greater than said specified value), the index in the local palette is expressed by m bits, and wherein the local palette is not created when n=m, and the local palette is created when n greater than m.
Because of this, when this color image decoding method is used, the color data amount which is used for decoding is significantly reduced and it is possible to use a simple decoding method. Because of this, it is possible to improve the refresh rate. Moreover, it is not necessary to decode the entire image, and it is acceptable to reproduce only the blocks which are needed for display. As the result, it is possible to minimize the memory for display, miniaturize it, and reduce the cost. Furthermore, it is possible to display the number of colors in the global palette and local palette with numbers of bits such as 1, 2, 4, 8, 16, and 32, respectively, and to improve the processing efficiency when the decoding process is performed in the CPU. Moreover, when m is the specified value or more, it is possible to control the capacity of the data which indicates the indexes because the value of m increases by one bit unit.
Moreover, in the present invention, in the color image decoding method, the predetermined value is set at 256 colors, the specified value is set at 5, and the size of one block is set at 32xc3x9732 pixels.
When the block size is set at 32xc3x9732 pixels, the maximum becomes 1,024 colors, and most images are accommodated within 256 colors. Thus, by setting the predetermined value at 256 colors, the present invention applies to most images and it is possible to reduce the memory and improve the refresh rate. Furthermore, when the number of colors in the block exceeds 16 colors and stays less than 32 colors, it can be expressed by five bits, when the number of colors exceeds 32 colors and stays less than 64 colors, it can be expressed by six bits, when the number of colors exceeds 64 colors and stays less than 128 colors, it can be expressed by 7 bits. It is possible to control the data capacity required for the color indexes to a small size. In particular, data such as a map has approximately 20 colors in many cases, so in a case such as that, it can be expressed by five bits, and it is possible to definitely minimize the capacity compared to eight bits when m is the x square of 2. In addition, when run length encoding is performed, 16 can be used as a maximum number of runs and it can be processed by four bits at that time.
Furthermore, in the present invention, a color image encoding method which inputs and encodes the color image data has a block division step which divides the input color image data into a plurality of blocks, a maintaining step which maintains the image data of the blocks, and a modeling method determination step which, when the image state in a block which was pre-scanned is temporarily run-length encoded, and the ratios where the value of the run becomes 1 and 2 are a specified value or less, run-length models, the block models using surrounding reference pixels when the specified value is exceeded.
Because of this, it is possible to use the most appropriate encoding method per block in the image, so the compression rate of the entire image improves and the decoding rate becomes fast in the case of decoding.
Furthermore, in the present invention, a color image encoding method which inputs and encodes the color image data includes the steps of counting the number of colors used in the input color image data, creating a global palette in which indexes corresponding to respective colors are listed when the number of colors used is a predetermined value or less, dividing the input color image data into a plurality of blocks, creating a local palette in which the indexes in the global palette are listed when the number of colors in a block is less than the number of colors in the global palette, assigning the indexes in the global palette to the input pixels when the number of colors in the block is the same as the number of colors in the global palette, encoding the color index, maintaining the image data of the block, and a modeling method determination step which, when the image state in a block which was pre-scanned is temporarily run-length encoded, and the ratios where the value of the run becomes 1 and 2 are a specified value or less, run-length models the block using surrounding reference pixels when the specified value is exceeded.
Because of this, if the color image encoding method is used, the data which becomes the object of encoding is significantly reduced and it is possible to minimize the required data capacity. Because of this, it is possible to use a simple compression method and improve the refresh rate. Moreover, prior to the image display, it is possible to decode only the blocks which are needed for display and to minimize the memory needed for display. Furthermore, because the most appropriate encoding method can be used per block in the image, the compression rate of an entire image can improve and the decoding rate becomes fast in the case of decoding.
Moreover, in the present invention, the color image encoding method takes a value within 15-25% as the specified value.
As a result, when the same pixel does not continue, or even though it continues, if two pixels have the specified value or more determined by a value of 15-25% in the block, the efficiency of the run-length encoding deteriorates so that it is possible to improve the compression rate by using the surrounding reference pixel modeling. Meanwhile, when the value is the specified value or less within 15-25% the run-length encoding shows better efficiency so that it is possible to improve the encoding efficiency by the run-length modeling. Because of this, whatever state the image is in, it is possible to encode the image by using the encoding model which has better efficiency in response to the characteristics of the blocks which divide the image so that the encoding efficiency of the entire image improves.
In addition, in the present invention, in the color image encoding method, in the case of the surrounding reference pixel modeling, it is shown by a fixed-length bit whether the pixel to be encoded is the same as a specific one of the surrounding pixels.
Thus, because the fixed-length is used in order to specify that that pixel is the same as a surrounding pixel, if hardware is used which can perform a bit shift, the encoding and decoding rate improves.
Moreover, in the present invention, a color image encoding method which inputs and encodes the color image data has a block division means which divides the input color image data into a plurality of blocks, a maintaining means which maintains the image data of the blocks, and a modeling method determination means which, when the image state in a block which was pre-scanned is temporarily run-length encoded, and the ratios where the value of the run becomes 1 and 2 are a specified value or less, run-length models, the block models using surrounding reference pixels when the specified value is exceeded.
Because of this, it is possible to use the most appropriate encoding method per block in the image, so the compression rate of the entire image improves and the decoding rate becomes fast in the case of decoding.
Moreover, in the present invention, a color image encoding device which inputs and encodes the color image data comprises a number of colors used counting means which counts the number of colors used in the input color image data, a global palette creation means which creates a global palette in which indexes corresponding to respective colors are listed when the number of colors used is a predetermined value or less, a block division means which divides the input color image data into a plurality of blocks, a local palette creation means which creates a local palette in which the indexes in the global palette are listed when the number of colors in a block is less than the number of colors in the global palette, a color index assigning means which assigns the indexes in the global palette to the input pixels when the number of colors in the block is the same as the number of colors in the global palette, and which otherwise assigns the indexes in the local palette to the input pixel, an encoding means which encodes the color indexes, a maintaining means which maintains the image data of the block, and a modeling method determination means which, when the image state in a block which was pre-scanned is temporarily run-length encoded, and the ratios where the value of the run becomes 1 and 2 are a specified value or less, run-length models the block using surrounding reference pixels when the specified value is exceeded.
Because of this, if the color image encoding method is used, the data which becomes the object of encoding is significantly reduced and it is possible to minimize the required data capacity. Because of this, it is possible to use a simple compression method and improve the refresh rate. Moreover, prior to the image display, it is possible to decode only the blocks which are needed for display and to minimize the memory needed for display. Furthermore, because the most appropriate encoding method can be used per block in the image, the compression rate of an entire image can improve and the decoding rate becomes fast in the case of decoding.
Moreover, in the present invention, the color image encoding method takes a value within 15-25% as the specified value.
As the result, when the same pixel does not continue, or even though it continues, if two pixels have the specified value or more determined by a value of 15-25% in the block, the efficiency of the run-length encoding deteriorates so that it is possible to improve the compression rate by using the surrounding reference pixel modeling. Meanwhile, when the value is the specified value or less within 15-25%, the run-length encoding shows better efficiency so that it is possible to improve the encoding efficiency by the run-length modeling. Because of this, whatever state the image is in, it is possible to encode the image by using the encoding model which has better efficiency in response to the characteristics of the blocks which divide the image so that the encoding efficiency of the entire image improves.
In addition, in the present invention, in the color image encoding method, in the case of the surrounding reference pixel modeling, it is shown by a fixed-length bit whether the pixel to be encoded is the same as a specific one of the surrounding pixels.
Thus, because the fixed-length is used, in order to specify that that pixel is the same as a surrounding pixel, if hardware is used which can perform a bit shift, the encoding and decoding rate improves.
Furthermore, in the present invention, a color image decoding method which decodes encoded color image data comprises a block decoding step which divides the color image data into a plurality of blocks and decodes the encoded data per respective block, wherein the block decoding step includes the steps of determining whether the block to be decoded is encoded by run-length modeling or by surrounding reference pixel modeling, and decoding by the run-length modeling or the surrounding reference pixel modeling based upon the determination result of the determination step.
Because of this, the pixels are decoded by the most appropriate decoding method per block in the image, so the decoding efficiency of the entire image improves.
Furthermore, in the present invention, a color image decoding method which decodes the encoded color image data includes the steps of identifying the number of colors used in the entire color image data to be decoded, calling the global palette in which indexes corresponding to respective colors are listed when the number of colors used is a predetermined value or less, and decoding data that was encoded by dividing the color image data into a plurality of blocks, wherein the block decoding step has a number of colors in the block identifying step which identifies the number of colors in the divided blocks, and a conditional alias decoding process which, when the number of colors which was identified by the number of colors in the block identifying step is less than the number of colors in the global palette, a column corresponding to the local palette in which the indexes in the global palette are listed is called from the values of the decoded color indexes and the colors of the global palette which is described in the local palette is decoded, and which, when the number of colors which was identified by the number of colors in the block identifying step is the same as the number of colors in the global palette, directly decodes the colors of the global palette from the values of the color indexes which were decoded, a determination step which determines whether the block to be decoded is encoded by the run-length modeling or the surrounding reference pixel modeling, and a decoding step which decodes by the run-length modeling or the surrounding reference pixel modeling based upon the determination result of the determination process.
Because of this, when this color image decoding method is used, it is possible to significantly reduce the color data amount which is used for decoding and to use a simple decoding method. Because of this, it is possible to improve the refresh rate. Furthermore, it is not necessary to decode the entire image, and it is acceptable to reproduce only the blocks which are needed for the display. As a result, it is possible to reduce the memory required for display, miniaturize the device which uses the decoding method, and reduce the cost. Moreover, because the pixels are decoded by the most appropriate decoding method per block in the image, the decoding efficiency of the entire image improves.
In addition, in the present invention, in the color image decoding method, in the case of decoding by the surrounding reference pixel modeling, it is shown by a fixed-length bit whether the pixel to be decoded is the same as a specific one of the surrounding pixels.
Thus, because the fixed-length is used in order to specify that that pixel is the same as the surrounding pixel, when hardware is used which can perform a bit shift, the rate improves in the case of decoding.
Furthermore, in the present invention, a color image decoding method which decodes encoded color image data includes the steps of dividing the color image data into a plurality of blocks and decoding the encoded data per respective block, wherein the block decoding means comprises a determination means which determines whether the block to be decoded is encoded by run-length modeling or by surrounding reference pixel modeling and a decoding means which decodes by the run-length modeling or the surrounding reference pixel modeling based upon the determination result of the determination means.
Because of this, the pixels are decoded by the most appropriate decoding method per block in the image, so the decoding efficiency of the entire image improves.
Furthermore, in the present invention, a color image decoding device which decodes the encoded color image data comprises a number of colors used identifying means which identifies the number of colors used in the entire color image data to be decoded, a global palette calling means which calls the global palette in which indexes corresponding to respective colors are listed when the number of colors used is a predetermined value or less, and a block decoding means which decodes data that was encoded by dividing the color image data into a plurality of blocks, wherein the block decoding means has a number of colors in the block identifying means which identifies the number of colors in the divided blocks, and a conditional alias decoding means which, when the number of colors which was identified by the number of colors in the block identifying means is less than the number of colors in the global palette, a column corresponding to the local palette in which the indexes in the global palette are listed is called from the values of the decoded color indexes and the colors of the global palette which is described in the local palette is decoded, and which, when the number of colors which was identified by the number of colors in the block identifying means is the same as the number of colors in the global palette, directly decodes the colors of the global palette from the values of the color indexes which were decoded, a determination means which determines whether the block to be decoded is encoded by the run-length modeling or the surrounding reference pixel modeling, and a decoding means which decodes by the run-length modeling or the surrounding reference pixel modeling based upon the determination result of the determination means.
Because of this, when this color image decoding device is used, it is possible to significantly reduce the color data amount which is used for decoding and to use a simple decoding means. Because of this, it is possible to improve the refresh rate. Furthermore, it is not necessary to decode the entire image, and it is acceptable to reproduce only the blocks which are needed for the display. As a result, it is possible to reduce the memory for display, miniaturize the device which uses the decoding method, and reduce the cost. Moreover, because the pixels are decoded by the most appropriate decoding means per block in the image, the decoding efficiency of the entire image improves.
In addition, in the present invention, in the color image decoding method, in the case of decoding by the surrounding reference pixel modeling, it is shown by a fixed-length bit whether the pixel to be decoded is the same as a specific one of the surrounding pixels.
Thus, because the fixed-length is used in order to specify that the pixel is the same as the surrounding pixel, when hardware is used which can perform a bit shift, the decoding rate improves.
Furthermore, in the present invention, a color image encoding method which inputs and encodes color image data includes the steps of dividing the input color image data into a plurality of blocks, scanning and maintaining the color image data to be encoded, run-length modeling when a pixel of a specified position is the same color as the previous pixel and is different from a pixel of one line before, copy mode forming which, when the pixel of the specified position is a different color from the previous pixel, forms a copy mode which compares the pixel of the one line before to the pixel of the specified position and copies the pixel of the one line before in the case of the same color, taking the number of continuous pixels for which the color is the same as the pixel of one line before as a number of copies, and encoding the value of the copy mode and the value of the number of copies along with the other color indexes which were run-length modeled and the normal value of the run.
Thus, the pixels are usually encoded by the run-length modeling, and when the run does not continue, the pixel of one line before is compared, and in the case of the same color, so-called copying will be carried out, so it is possible to improve the compression rate even if various images such as vertical and horizontal patterns appear in the image.
Furthermore, in the present invention, a color image encoding method which inputs and encodes the color image data includes the steps of counting the number of colors used in the input color image data, creating a global palette in which indexes corresponding to respective colors are listed when the number of colors used is a predetermined value or less, dividing the input color image data into a plurality of blocks, creating a local palette in which the indexes in the global palette are listed when the number of colors in a block is less than the number of colors in the global palette, assigning the indexes in the local palette to the input pixels when the number of colors in the block is the same as the number of colors in the global palette, and otherwise assigning the indexes in the local palette to the input pixels, and encoding the color indexes, maintaining the color image data to be encoded, run-length modeling when a pixel of a specified position is the same color as the previous pixel and is a different color from a pixel of one line before, copy mode forming which, when the pixel of the specified position is the same color as the previous pixel and the pixel of the next position is a different color from the previous pixel, forms a copy mode which compares the pixel of the one line before the pixel of the specified position and copies the pixel of the one previous line in the case of the same color, taking the number of continuous pixels for which the color is the same as the pixel of the one line before as a number of copies, and encoding the value of the copy mode and the value of the number of copies along with the other color indexes which were run-length modeled and the normal value of the run.
Because of this, this color image encoding method is used, the data which becomes the object of encoding is significantly decreased and it is possible to minimize the required data capacity. Because of this, it is possible to use a simple compression method and to improve the refresh rate. Furthermore, prior to the image display, it is possible to decode only the blocks which are needed for display and to minimize the memory required for display. In addition, the pixels are usually encoded by run-length modeling, and when a run does not continue, a pixel of the one line before is compared, and in the case of the same color, so-called copying will be carried out, so it is possible to improve the compression rate even if various images such as vertical and horizontal patterns appear in the image.
Moreover, in the present invention, in the color image encoding method, the scan is raster-scanned in the horizontal direction and the pixel of one line before is defined as the pixel that is directly above, and a copy mode is shown using one of the color indexes.
Because of this, with respect to an image of vertical patterns, the compression efficiency does not improve in the conventional run-length encoding technology, but the compression rate improves with vertical patterns and also with horizontal patterns in the present invention.
Furthermore, in the present invention, a color image encoding device which inputs and encodes color image data comprises a block division means which divides the input color image data into a plurality of blocks, a maintaining means which scans and maintains the color image data to be encoded, a run-length modeling means which run-length models when a pixel of a specified position is the same color as the previous pixel and is a different color from a pixel of one line before, a copy mode formation means which, when the pixel of the specified position is a different color from the previous pixel, forms a copy mode which compares the pixel of the one line before to the pixel of the specified position and copies the pixel of the one line before in the case of the same color, a number of copies formation means which takes the number of continuous pixels for which the color is the same as the pixel of one line before as a number of copies, and an encoding means which encodes the value of the copy mode and the value of the number of copies along with the other color indexes which were run-length modeled and the normal value of the run.
Thus, the pixels are usually encoded by the run-length modeling, and when the run does not continue, the pixel of one line before is compared, and in the case of the same color, so-called copying will be carried out, so it is possible to improve the compression rate even if various images such as vertical and horizontal patterns appear in the image.
Furthermore, in the present invention, a color image encoding device which inputs and encodes the color image data comprises a number of colors used counting means which counts the number of colors used in the input color image data, a global palette creation means which creates a global palette in which indexes corresponding to respective colors are listed when the number of colors used is a predetermined value or less, a block division means which divides the input color image data into a plurality of blocks, a local palette creation means which creates a local palette in which the indexes in the global palette are listed when the number of colors in a block is less than the number of colors in the global palette, a color index assigning means which otherwise assigns the indexes in the local palette to the input pixels when the number of colors in the block is the same as the number of colors in the global palette, and which otherwise assigns the indexes in the local palette to the input pixels, and an encoding means which encodes the color indexes, a maintaining means which scans and maintains the color image data to be encoded, a run-length modeling means which run-length models when the pixel of a specified position is the same color as the previous pixel and is a different color from a pixel of one line before, a copy mode formation means which, when the pixel of the predetermined position is a different color from the previous pixel, forms a copy mode which compares a pixel of one line before to the pixel of the specified position and copies the pixel of one line before in the case of the same color, a number of copies formation means which takes the number of continuous pixels for which the color is the same as the pixel of one line before as a number of copies, and an encoding means which encodes the value of the copy mode and the value of the number of copies along with the other color indexes which were run-length modeled and the normal value of the run.
Because of this, this color image encoding device is used, the data which becomes the object of encoding is significantly decreased and it is possible to minimize the required data capacity. Because of this, it is possible to use a simple compression method and to improve the refresh rate. Furthermore, prior to the image display, it is possible to decode only the blocks which are needed for display and to minimize the memory required for display. In addition, the pixels are usually encoded by run-length modeling, and when a run does not continue, a pixel of the one line before is compared, and in the case of the same color, so-called copying will be carried out, so it is possible to improve the compression rate even if various images such as vertical and horizontal patterns appear in the image.
Moreover, in the present invention, in the color image encoding method, the scan is raster-scanned in the horizontal direction and the pixel of one line before is defined as the pixel that is directly above, and a copy mode is shown using one of the color indexes.
Because of this, with respect to an image of vertical patterns, the compression efficiency does not improve in the conventional run-length encoding technology, but the compression rate improves with vertical patterns and also with horizontal patterns in the present invention.
Furthermore, in the present invention, a color image decoding method which decodes encoded color image data includes the steps of dividing the color image data into a plurality of blocks and decoding the encoded data in each block, wherein the block decoding step has a run-length decoding step which, when a copy mode is included that indicates copying of the pixel of one line before the pixel which is decoded in data which was run-length encoded, decodes the same color as the pixel of one line before as many times as the copy mode continues.
Thus, the pixels are usually decoded by the run-length modeling, and when the run does not continue, a pixel of one line before is compared, and in the case of the same color, so-called copying will be carried out, so it is possible to improve the decoding efficiency even if various images such as vertical and horizontal patterns appear in the image.
Furthermore, in the present invention, a color image decoding method which decodes the encoded color image data includes the steps of identifying the number of colors used in the entire color image data to be decoded, calling the global palette in which indexes corresponding to respective colors are listed when the number of colors used is a predetermined value or less, decoding data that was encoded by dividing the color image data into a plurality of blocks, wherein the block decoding step has a number of colors in the block identifying step which identifies the number of colors in the divided blocks, and a conditional alias decoding step which, when the number of colors which was identified by the number of colors in the block identifying process is less than the number of colors in the global palette, a column corresponding to the local palette in which the indexes in the global palette are listed is called from the values of the decoded color indexes and the colors of the global palette which is described in the local palette is decoded, and which, when the number of colors which was identified by the number of colors in the block identifying process is the same as the number of colors in the global palette, directly decodes the colors of the global palette from the values of the color indexes which were decoded, and run-length decoding step which, when a copy mode is included that indicates copying of the pixel of one line before the pixel which is decoded in data which was run-length encoded, decodes the same color as the pixel of one line before as many times as the copy mode continues.
Because of this, when this color image decoding method is used, it is possible to significantly reduce the data amount of the color which is used for decoding and to use a simple decoding method. Because of this, it is possible to improve the refresh rate. Furthermore, it is not necessary to decode the entire image, and it is acceptable to reproduce only the blocks which are needed for the display. As the result, it is possible to reduce the memory required for display, miniaturize the device which uses the decoding method, and reduce the cost. Furthermore, the pixels are usually decoded by the run-length modeling, and when a run does not continue, a pixel of one line before is compared, and in the case of the same color, so-called copying will be carried out, so it is possible to improve the decoding efficiency even if various images such as vertical and horizontal patterns appear in the image.
Moreover, in the present invention, in the color image decoding method, the line scan is raster-scanned and the pixel of one line before is defined as the pixel directly above, and a copy mode is shown using one of the color indexes that show the pixels of the image data.
Because of this, with respect to an image of a vertical pattern, the decoding rate does not improve in the conventional run-length decoding technology, but the decoding rate improves with the vertical patterns and with horizontal patterns in the present invention.
Furthermore, in the present invention, a color image decoding device which decodes encoded color image data comprises a block decoding means which divides the color image data into a plurality of blocks and decodes the encoded data in each block, wherein the block decoding means has a run-length decoding means which, when a copy mode is included that indicates copying of the pixel of one line before the pixel which is decoded in data which was run-length encoded, decodes the same color as the pixel of one line before as many times as the copy mode continues.
Thus, the pixels are usually decoded by the run-length modeling, and when the run does not continue, a pixel of one line before is compared, and in the case of the same color, so-called copying will be carried out, so it is possible to improve the decoding efficiency even if various images such as vertical and horizontal patterns appear in the image.
Furthermore, in the present invention, a color image decoding device which decodes the encoded color image data comprises a number of colors used identifying means which identifies the number of colors used in the entire color image data to be decoded, a global palette calling means which calls the global palette in which indexes corresponding to respective colors are listed when the number of colors used is a predetermined value or less, and a block decoding means which decodes data that was encoded by dividing the color image data into a plurality of blocks, wherein the block decoding means has a number of colors in the block identifying means which identifies the number of colors in the divided blocks, and a conditional alias decoding means which, when the number of colors which was identified by the number of colors in the block identifying means is less than the number of colors in the global palette, a column corresponding to the local palette in which the indexes in the global palette are listed is called from the values of the decoded color indexes and the colors of the global palette which is described in the local palette is decoded, and which, when the number of colors which was identified by the number of colors in the block identifying means is the same as the number of colors in the global palette, directly decodes the colors of the global palette from the values of the color indexes which were decoded, and a run-length decoding means which, when a copy mode is included that indicates copying of the pixel of one line before the pixel which is decoded in data which was run-length encoded, decodes the same color as the pixel of one line before as many times as the copy mode continues.
Because of this, when this color image decoding device is used, it is possible to significantly reduce the data amount of the color which is used for decoding and to use a simple decoding method. Because of this, it is possible to improve the refresh rate. Furthermore, it is not necessary to decode the entire image, and it is acceptable to reproduce only the blocks which are needed for the display. As the result, it is possible to reduce the memory required for display, miniaturize the device which uses the decoding method, and reduce the cost. Furthermore, the pixels are usually decoded by the run-length modeling, and when a run does not continue, a pixel of one line before is compared, and in the case of the same color, so-called copying will be carried out, so it is possible to improve the decoding efficiency even if various images such as vertical and horizontal patterns appear in the image.
Moreover, in the present invention, in the color image decoding method, the line scan is raster-scanned and the pixel of one line before is defined as the pixel directly above, and a copy mode is shown using one of the color indexes which show the pixels of the image data.
Because of this, with respect to an image of a vertical pattern, the decoding rate does not improve in the conventional run-length decoding technology, but the decoding rate improves with the vertical patterns and with horizontal patterns in the present invention.
In each invention of the present application, prior to dividing the image and encoding and/or decoding, the way of holding the palette data, encoding, and the like are well designed. With respect to the design of the way of holding the palette data, by focusing on reducing of the numbers of colors of each block when the image is divided into blocks, as compared to the number of colors when the pixels are seen as an entire image, at least two palettes which have a fewer number of colors are provided in response to the level of the number of colors. The two palettes can be appropriately combined and used in response to the number of colors of the blocks, and result in less encoding and decoding data amount, and improvement of the encoding efficiency and decoding rate.